#include "csort.h"

void blblSort(int ary[], int len){
    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - i - 1; j++){
            if(ary[j] > ary[j + 1]){
                int temp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = temp;
            }
        }
    }
}

void selectSort(int ary[], int len){
    for(int i = 0; i < len; i++){
        int min = i;

        for(int j = i + 1; j < len; j++){
            if(ary[j] < ary[min]){
                min = j;
            }
        }

        if(min != i){
            int temp = ary[min];
            ary[min] = ary[i];
            ary[i] = temp;
        }
    }
}

void insertSort(int ary[], int len){
    for(int i = 1; i < len; i++){
        int key = ary[i];

        int j = i - 1;
        while(j >= 0 && ary[j] > key){
            j--;
        }

        ary[j + 1] = key;
    }
}

void quickSort(int ary[], int len, int left, int right){
    if(left >= right){
        return;
    }

    int i = left;
    int j = right;
    int key = ary[i];

    while(i < j){
        while(i < j && ary[j] > key){
            j--;
        }

        if(i < j){
            ary[i] = ary[j];
            i++;
        }

        while(i < j && ary[i] < key){
            i++;
        }

        if(i < j){
            ary[j] = ary[i];
            j--;
        }

        ary[i] = key;
    }

    quickSort(ary, len, left, i - 1);
    quickSort(ary, len, i + 1, right);
}

// void mergeSort(int ary[], int len, int left, int right){
//     if (left >= right)
//     {
//         return;
//     }
//     int mid = (left + right) / 2;
//     mergeSort(ary, len, left, mid);
//     mergeSort(ary, len, mid + 1, right);

//     int k = 0; 
//     int i = left, j = mid + 1;
//     vector<int> tmp;
//     while (i <= mid && j <= right)
//     {
//         if (vec[i] <= vec[j])
//         {
//             tmp.push_back(vec[i++]);
//         }
//         else
//         {
//             tmp.push_back(vec[j++]);
//         }
//     }
//     while (i <= mid)
//     {
//         tmp.push_back(vec[i++]);
//     }
//     while (j <= right)
//     {
//         tmp.push_back(vec[j++]);
//     }
//     for (i = left, k = 0; i <= right; ++i)
//     {
//         vec[i] = tmp[k++];
//     }
// }